package top.lywivan.unionfind;

/**
 * @desc 并查集实现
 * @author:ivan.liu
 */
public class UnionFind {
    //定义集合的数量
    int count=0;
    //定义每个元素的父元素，father[i]=j表示i的父元素是j
    int[] father;

    /**
     * 构造方法，生成num个集合
     * @param num
     */
    public UnionFind(int num){
        this.count=num;
        this.father=new int[num];
        //初始时，每个元素单独组成一个集合
        for (int i = 0; i < num; i++) {
            father[i]=i;
        }
    }

    /**
     * 获取元素n所在的集合，返回集合的顶级父元素
     * @param n
     * @return
     */
    public int find(int n){
        //基于循环实现
        /*while (father[n]!=n){
            n=father[n];
        }
        return n;*/
        //基于递归实现
        if(father[n]==n){
            return n;
        }
        //将当前节点的父节点指向原来父节点的根节点，实现路径压缩
        father[n]=find(father[n]);
        return father[n];
    }

    /**
     * 合并两个元素所在的集合
     * @param p
     * @param q
     */
    public void union(int p,int q){
        //获取p和q所在的集合
        int p_father = find(p);
        int q_father = find(q);
        if(p_father==q_father){
            return;
        }
        //合并两个集合的代表元素
        father[p_father]=q_father;
        count--;
    }

    /**
     * 获取集合数量
     * @return
     */
    public int getCount(){
        return count;
    }
}
